package middle;

import java.util.ArrayList;
import java.util.List;
import util.PrintUtils;

public class Solution_120 {
    public int minimumTotal(List<List<Integer>> triangle) {
        int[] array = new int[triangle.size()];
        for (int j = 0; j < triangle.size(); j++) {
            int pre = 0;
            List<Integer> list = triangle.get(j);
            for (int i = 0; i < list.size(); i++) {
                if (i == 0) {
                    int temp = list.get(i) + array[i];
                    pre = array[i];
                    array[i] = temp;
                } else if (i == (list.size() -1)) {
                    array[i] = list.get(i) + pre;
                } else {
                    int temp = list.get(i) + Math.min(pre, array[i]);
                    pre = array[i];
                    array[i] = temp;
                }
            }
        }
        int min = Integer.MAX_VALUE;
        for (Integer num : array) {
            min = Math.min(min, num);
        }
        return min;
    }

    public static void main(String[] args) {
        Solution_120 model = new Solution_120();
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> temp;
        temp = new ArrayList<>();
        temp.add(2);
        list.add(temp);

        temp = new ArrayList<>();
        temp.add(3);
        temp.add(4);
        list.add(temp);

        temp = new ArrayList<>();
        temp.add(6);
        temp.add(5);
        temp.add(7);
        list.add(temp);

        temp = new ArrayList<>();
        temp.add(4);
        temp.add(1);
        temp.add(8);
        temp.add(3);
        list.add(temp);
        System.out.println(model.minimumTotal(list));
    }
}
